playlist.c 19 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004
  1. #include <assert.h>
  2. #include <errno.h>
  3. #include <limits.h>
  4. #include <stddef.h>
  5. #include <stdint.h>
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9. #include <sys/stat.h>
  10. #include <dirent.h>
  11. #include <fnmatch.h>
  12. #include <glob.h>
  13. #include <regex.h>
  14. #include <err.h>
  15. #include <sysexits.h>
  16. #include "playlist.h"
  17. #include "util.h"
  18. #define PGDELTA 4
  19. enum {
  20. PLCMPNORM,
  21. PLCMPGLOB,
  22. PLCMPBRE,
  23. PLCMPERE
  24. };
  25. enum {
  26. PEITEM,
  27. PEGRP
  28. };
  29. enum {
  30. PGNORM,
  31. PGSHUF,
  32. PGRAND
  33. };
  34. enum {
  35. PGLOST = 1
  36. };
  37. struct pentry;
  38. struct pgroup {
  39. struct pgroup *parent;
  40. struct pentry **entries;
  41. size_t size;
  42. size_t count;
  43. size_t index;
  44. int flags;
  45. int type;
  46. };
  47. struct pitem {
  48. char *path;
  49. };
  50. union punion {
  51. struct pgroup g;
  52. struct pitem e;
  53. };
  54. struct pentry {
  55. int type;
  56. union punion u;
  57. };
  58. struct hlist {
  59. struct pitem **entries;
  60. size_t size;
  61. size_t begin;
  62. size_t end;
  63. size_t index;
  64. int lost;
  65. };
  66. struct playlist {
  67. struct hlist hl;
  68. struct pgroup pg;
  69. struct pgroup *ag;
  70. void (*onadd)(void *, const char *);
  71. void (*onrem)(void *, const char *);
  72. void *addctx;
  73. void *remctx;
  74. int flags;
  75. };
  76. static void pe_free(struct pentry *);
  77. static void *plcmp_init(const char *, int);
  78. static void plcmp_fini(void *, int);
  79. static int plcmp_call(void *, const char *, int);
  80. static struct pitem *pl_next(struct playlist *, struct pgroup *);
  81. static void pl_rem(struct playlist *, struct pgroup *,
  82. void *, int, void(*)(void *, const char *),
  83. void *);
  84. static int pl_remove(struct playlist *, struct pgroup *,
  85. size_t, void(*)(void *, const char *),
  86. void *);
  87. static void pg_init(struct pgroup *, int);
  88. static void pg_fini(struct pgroup *);
  89. static void pg_append(struct pgroup *, struct pentry *);
  90. static struct pitem *pg_current(struct pgroup *);
  91. static struct pgroup *pg_parent(struct pgroup *, struct pitem *);
  92. static void pg_reset(struct pgroup *);
  93. static struct pitem *pg_search(struct pgroup *, void *, int, int);
  94. static int pg_goto(struct pgroup *, struct pitem *);
  95. static void hl_init(struct hlist *, size_t);
  96. static void hl_fini(struct hlist *);
  97. static void hl_append(struct hlist *, struct pitem *);
  98. static int hl_remove(struct hlist *, struct pitem *);
  99. static void hl_rem(struct hlist *, void *, int);
  100. static struct pitem *hl_current(struct hlist *);
  101. static struct pitem *hl_next(struct hlist *);
  102. static struct pitem *hl_prev(struct hlist *);
  103. static struct pitem *hl_search(struct hlist *, void *, int);
  104. static int hl_goto(struct hlist *, struct pitem *);
  105. static int pl_gtype(int);
  106. static int pl_stype(int);
  107. static int de_nodot(const struct dirent *);
  108. struct playlist *
  109. playlist_create(size_t hsize, int flags)
  110. {
  111. struct playlist *pl;
  112. if ((pl = malloc(sizeof(*pl))) == NULL)
  113. err(EX_OSERR, "playlist_create");
  114. hl_init(&pl->hl, hsize);
  115. if ((flags & PLGTYPE) == PLGNONE)
  116. flags = (flags & ~PLGTYPE) | PLGNORM;
  117. pg_init(&pl->pg, pl_gtype(flags));
  118. pl->ag = &pl->pg;
  119. pl->flags = flags;
  120. pl->onadd = NULL;
  121. pl->onrem = NULL;
  122. pl->addctx = NULL;
  123. pl->remctx = NULL;
  124. return (pl);
  125. }
  126. void
  127. playlist_destroy(struct playlist *pl)
  128. {
  129. assert(pl != NULL);
  130. hl_fini(&pl->hl);
  131. pg_fini(&pl->pg);
  132. free(pl);
  133. }
  134. void
  135. playlist_loop(struct playlist *pl)
  136. {
  137. assert(pl != NULL);
  138. pg_reset(&pl->pg);
  139. }
  140. void
  141. playlist_onadd(struct playlist *pl, void (*cb)(void *, const char *),
  142. void *ctx)
  143. {
  144. assert(pl != NULL);
  145. pl->onadd = cb;
  146. pl->addctx = ctx;
  147. }
  148. void
  149. playlist_onrem(struct playlist *pl, void (*cb)(void *, const char *),
  150. void *ctx)
  151. {
  152. assert(pl != NULL);
  153. pl->onrem = cb;
  154. pl->remctx = ctx;
  155. }
  156. void
  157. playlist_gbegin(struct playlist *pl, int flags)
  158. {
  159. struct pentry *e;
  160. assert(pl != NULL);
  161. if ((flags & PLGTYPE) == PLGNONE)
  162. flags = (flags & ~PLGTYPE) | (pl->flags & PLGTYPE);
  163. if ((e = malloc(sizeof(*e))) == NULL)
  164. err(EX_OSERR, "playlist_gbegin");
  165. e->type = PEGRP;
  166. pg_init(&e->u.g, pl_gtype(flags));
  167. pg_append(pl->ag, e);
  168. pl->ag = &e->u.g;
  169. }
  170. int
  171. playlist_gend(struct playlist *pl)
  172. {
  173. assert(pl != NULL && pl->ag != NULL);
  174. if (pl->ag->parent == NULL)
  175. return (-1);
  176. pl->ag = pl->ag->parent;
  177. return (0);
  178. }
  179. void
  180. playlist_append(struct playlist *pl, const char *path)
  181. {
  182. struct pentry *e;
  183. assert(pl != NULL && path != NULL);
  184. if ((e = malloc(sizeof(*e))) == NULL)
  185. err(EX_OSERR, "playlist_append");
  186. e->type = PEITEM;
  187. if ((e->u.e.path = strdup(path)) == NULL)
  188. err(EX_OSERR, "playlist_append");
  189. pg_append(pl->ag, e);
  190. if (pl->onadd != NULL)
  191. pl->onadd(pl->addctx, e->u.e.path);
  192. }
  193. int
  194. playlist_add(struct playlist *pl, const char *pat, int flags)
  195. {
  196. struct dirent **de;
  197. struct stat st;
  198. glob_t gl;
  199. char *s;
  200. size_t i;
  201. int l;
  202. int n;
  203. int g;
  204. assert(pl != NULL && pat != NULL);
  205. if ((flags & PLSTYPE) == PLSAUTO)
  206. flags = (flags & ~PLSTYPE) | ((pl->flags & PLSTYPE)
  207. == PLSAUTO ? PLSCMP : (pl->flags & PLSTYPE));
  208. if ((g = (flags & PLGTYPE) != PLGNONE))
  209. playlist_gbegin(pl, pl_gtype(flags));
  210. flags = (flags & ~PLGTYPE) | PLGNONE;
  211. switch (flags & PLSTYPE) {
  212. case PLSCMP:
  213. if (stat(pat, &st) != 0)
  214. return (-1);
  215. if ((flags & PLRTYPE) != PLRNONE &&
  216. S_ISDIR(st.st_mode)) {
  217. for (l = strlen(pat); pat[l - 1] == '/'; l--)
  218. /* do nothing */;
  219. if ((n = scandir(pat, &de, &de_nodot,
  220. &alphasort)) < 0)
  221. return (-1);
  222. for (i = 0; i < n; i++) {
  223. if ((s = malloc(l +
  224. strlen(de[i]->d_name) + 2)) == NULL)
  225. err(EX_OSERR, "playlist_add");
  226. (void)sprintf(s, "%.*s/%s", l, pat,
  227. de[i]->d_name);
  228. (void)playlist_add(pl, s,
  229. (flags & PLRTYPE) != PLRFULL ?
  230. ((flags & ~PLRTYPE) | PLRNONE) :
  231. flags);
  232. free(s);
  233. free(de[i]);
  234. }
  235. free(de);
  236. } else if (S_ISREG(st.st_mode)) {
  237. playlist_append(pl, pat);
  238. } else
  239. return (-1);
  240. break;
  241. case PLSGLOB:
  242. if (glob(pat, 0, NULL, &gl) != 0)
  243. return (-1);
  244. for (i = 0; i < gl.gl_pathc; i++)
  245. playlist_add(pl, gl.gl_pathv[i],
  246. (flags & ~PLSTYPE) | PLSCMP);
  247. globfree(&gl);
  248. break;
  249. case PLSBRE:
  250. /* FALLTHROUGH */
  251. case PLSERE:
  252. errno = EINVAL;
  253. return (-1);
  254. default:
  255. abort();
  256. }
  257. return (g ? playlist_gend(pl) : 0);
  258. }
  259. int
  260. playlist_rem(struct playlist *pl, const char *pat, int flags)
  261. {
  262. void *cmp;
  263. int s;
  264. assert(pl != NULL && pat != NULL);
  265. if ((flags & PLSTYPE) == PLSAUTO)
  266. flags = (flags & ~PLSTYPE) | ((pl->flags & PLSTYPE)
  267. == PLSAUTO ? PLSGLOB : (pl->flags & PLSTYPE));
  268. s = pl_stype(flags);
  269. if ((cmp = plcmp_init(pat, s)) == NULL)
  270. return (-1);
  271. hl_rem(&pl->hl, cmp, s);
  272. pl_rem(pl, &pl->pg, cmp, s, pl->onrem, pl->remctx);
  273. plcmp_fini(cmp, s);
  274. return (playlist_current(pl) != NULL ? 0 : 1);
  275. }
  276. const char *
  277. playlist_current(struct playlist *pl)
  278. {
  279. struct pitem *e;
  280. assert(pl != NULL);
  281. if (pl->hl.lost)
  282. return (NULL);
  283. if ((e = hl_current(&pl->hl)) != NULL)
  284. return (e->path);
  285. if ((e = pg_current(&pl->pg)) != NULL)
  286. return (e->path);
  287. return (NULL);
  288. }
  289. const char *
  290. playlist_next(struct playlist *pl)
  291. {
  292. struct pitem *e;
  293. int l;
  294. assert(pl != NULL);
  295. l = hl_current(&pl->hl) != NULL || pl->hl.lost;
  296. if ((e = hl_next(&pl->hl)) != NULL)
  297. return (e->path);
  298. if ((e = pg_current(&pl->pg)) != NULL) {
  299. if (l)
  300. return (e->path);
  301. hl_append(&pl->hl, e);
  302. }
  303. if ((e = pl_next(pl, &pl->pg)) != NULL)
  304. return (e->path);
  305. return (NULL);
  306. }
  307. const char *
  308. playlist_prev(struct playlist *pl)
  309. {
  310. struct pitem *e;
  311. assert(pl != NULL);
  312. if ((e = hl_prev(&pl->hl)) != NULL)
  313. return (e->path);
  314. return (NULL);
  315. }
  316. const char *
  317. playlist_search(struct playlist *pl, const char *pat, int flags)
  318. {
  319. struct pgroup *pg;
  320. struct pitem *e;
  321. void *cmp;
  322. int s;
  323. assert(pl != NULL && pat != NULL);
  324. s = pl_stype(flags);
  325. if ((cmp = plcmp_init(pat, s)) == NULL)
  326. return (NULL);
  327. if ((e = hl_search(&pl->hl, cmp, s)) != NULL) {
  328. if (flags & PLGOTO)
  329. (void)hl_goto(&pl->hl, e);
  330. } else if ((e = pg_search(&pl->pg, cmp, s, flags & PLLOOP))
  331. != NULL) {
  332. if ((flags & PLGOTO) && pg_goto(&pl->pg, e) != 0) {
  333. pg_reset(&pl->pg);
  334. (void)pg_goto(&pl->pg, e);
  335. pg = pg_parent(&pl->pg, e);
  336. assert(pg != NULL);
  337. if (pg->type == PGSHUF) {
  338. memswap(&pg->entries[0],
  339. &pg->entries[pg->index],
  340. sizeof(pg->entries[0]));
  341. e = &pg->entries[0]->u.e;
  342. pg->index = 0;
  343. }
  344. }
  345. }
  346. plcmp_fini(cmp, s);
  347. return (e != NULL ? e->path : NULL);
  348. }
  349. void
  350. pe_free(struct pentry *e)
  351. {
  352. assert(e != NULL);
  353. switch (e->type) {
  354. case PEITEM:
  355. free(e->u.e.path);
  356. break;
  357. case PEGRP:
  358. pg_fini(&e->u.g);
  359. break;
  360. default:
  361. abort();
  362. }
  363. free(e);
  364. }
  365. void *
  366. plcmp_init(const char *pat, int type)
  367. {
  368. regex_t *r;
  369. assert(pat != NULL);
  370. switch(type) {
  371. case PLCMPNORM:
  372. /* FALLTHROUGH */
  373. case PLCMPGLOB:
  374. return (strdup(pat));
  375. case PLCMPBRE:
  376. /* FALLTHROUGH */
  377. case PLCMPERE:
  378. if ((r = malloc(sizeof(*r))) == NULL)
  379. return (NULL);
  380. if (regcomp(r, pat, REG_NOSUB | (type == PLCMPERE ?
  381. REG_EXTENDED : REG_BASIC)) != 0) {
  382. free(r);
  383. return (NULL);
  384. }
  385. return (r);
  386. }
  387. abort();
  388. }
  389. void
  390. plcmp_fini(void *cmp, int type)
  391. {
  392. switch(type) {
  393. case PLCMPNORM:
  394. return;
  395. case PLCMPGLOB:
  396. return;
  397. case PLCMPBRE:
  398. /* FALLTHROUGH */
  399. case PLCMPERE:
  400. regfree(cmp);
  401. break;
  402. }
  403. abort();
  404. }
  405. int
  406. plcmp_call(void *cmp, const char *str, int type)
  407. {
  408. assert(cmp != NULL);
  409. switch(type) {
  410. case PLCMPNORM:
  411. return (strcmp(cmp, str));
  412. case PLCMPGLOB:
  413. return (fnmatch(cmp, str, 0));
  414. case PLCMPBRE:
  415. /* FALLTHROUGH */
  416. case PLCMPERE:
  417. return (regexec(cmp, str, 0, NULL, 0));
  418. }
  419. abort();
  420. }
  421. struct pitem *
  422. pl_next(struct playlist *pl, struct pgroup *pg)
  423. {
  424. struct pitem *e;
  425. assert(pl != NULL && pg != NULL);
  426. if (pg->index >= pg->count && pg->type != PGRAND)
  427. return (NULL);
  428. if (!(pg->flags & PGLOST) && pg->index < pg->count &&
  429. pg->entries[pg->index]->type == PEGRP &&
  430. pg->entries[pg->index]->u.g.type != PGRAND) {
  431. if ((e = pl_next(pl, &pg->entries[pg->index]->u.g))
  432. != NULL) {
  433. pg->flags &= ~PGLOST;
  434. return (e);
  435. }
  436. pg_reset(&pg->entries[pg->index]->u.g);
  437. }
  438. for (;;) {
  439. /* Select the next entry in this group */
  440. switch (pg->type) {
  441. case PGNORM:
  442. /* FALLTHROUGH */
  443. case PGSHUF:
  444. if (!(pg->flags & PGLOST) &&
  445. pg->index < pg->count)
  446. pg->index++;
  447. break;
  448. case PGRAND:
  449. pg->index = arc4random_uniform(pg->count);
  450. break;
  451. default:
  452. abort();
  453. }
  454. if (pg->index >= pg->count)
  455. return (NULL);
  456. pg->flags &= ~PGLOST;
  457. if (pg->entries[pg->index]->type == PEITEM)
  458. return (&pg->entries[pg->index]->u.e);
  459. else if ((e = pl_next(pl, &pg->entries[pg->index]->u.g))
  460. != NULL)
  461. return (e);
  462. else if (pg->entries[pg->index]->u.g.count > 0)
  463. pg_reset(&pg->entries[pg->index]->u.g);
  464. else
  465. pl_remove(pl, pg, pg->index, NULL, NULL);
  466. }
  467. return (NULL);
  468. }
  469. void
  470. pl_rem(struct playlist *pl, struct pgroup *pg, void *cmp, int type,
  471. void (*cb)(void *, const char *), void *ctx)
  472. {
  473. size_t i;
  474. assert(pl != NULL && pg != NULL && cmp != NULL);
  475. for (i = 0; i < pg->count; i++)
  476. switch (pg->entries[i]->type) {
  477. case PEITEM:
  478. if (plcmp_call(cmp, pg->entries[i]->u.e.path,
  479. type) == 0)
  480. (void)pl_remove(pl, pg, i--, cb, ctx);
  481. break;
  482. case PEGRP:
  483. pl_rem(pl, &pg->entries[i]->u.g, cmp, type, cb,
  484. ctx);
  485. if (pg->entries[i]->u.g.count == 0) {
  486. (void)pl_remove(pl, pg, i--, cb, ctx);
  487. }
  488. break;
  489. default:
  490. abort();
  491. }
  492. }
  493. int
  494. pl_remove(struct playlist *pl, struct pgroup *pg, size_t index,
  495. void (*cb)(void *, const char *), void *ctx)
  496. {
  497. assert(pg != NULL);
  498. if (index >= pg->count)
  499. return (-1);
  500. if (pg->entries[index]->type == PEITEM && cb != NULL)
  501. cb(ctx, pg->entries[index]->u.e.path);
  502. if (pg->entries[index]->type == PEGRP) {
  503. if (pl == NULL)
  504. return (-1);
  505. if (&pg->entries[index]->u.g == pl->ag)
  506. pl->ag = pg->entries[index]->u.g.parent;
  507. }
  508. pe_free(pg->entries[index]);
  509. if (index + 1 < pg->count)
  510. (void)memmove(&pg->entries[index],
  511. &pg->entries[index + 1], sizeof(pg->entries[0]) *
  512. (pg->count - index - 1));
  513. if (index == pg->index)
  514. pg->flags |= PGLOST;
  515. else if (index < pg->index)
  516. pg->index--;
  517. pg->count--;
  518. return (0);
  519. }
  520. void
  521. pg_init(struct pgroup *pg, int type)
  522. {
  523. assert(pg != NULL);
  524. pg->parent = NULL;
  525. pg->entries = NULL;
  526. pg->size = 0;
  527. pg->count = 0;
  528. pg->index = 0;
  529. pg->flags = PGLOST;
  530. pg->type = type;
  531. }
  532. void
  533. pg_fini(struct pgroup *pg)
  534. {
  535. assert(pg != NULL);
  536. while (pl_remove(NULL, pg, 0, NULL, NULL) == 0)
  537. /* do nothing */;
  538. if (pg->entries != NULL)
  539. free(pg->entries);
  540. pg_init(pg, pg->type);
  541. }
  542. void
  543. pg_append(struct pgroup *pg, struct pentry *e)
  544. {
  545. assert(pg != NULL && e != NULL);
  546. *(struct pentry **)allot((void **)&pg->entries, &pg->size,
  547. pg->count, sizeof(e), PGDELTA) = e;
  548. if (e->type == PEGRP)
  549. e->u.g.parent = pg;
  550. pg->count++;
  551. if (pg->type == PGSHUF && pg->count > pg->index) {
  552. if ((pg->flags & PGLOST) && pg->count - pg->index > 2)
  553. memshuffle(pg->entries + pg->index,
  554. pg->count - pg->index,
  555. sizeof(pg->entries[0]));
  556. else if (pg->count - pg->index >= 2)
  557. memshuffle(pg->entries + pg->index + 1,
  558. pg->count - pg->index - 1,
  559. sizeof(pg->entries[0]));
  560. }
  561. }
  562. struct pitem *
  563. pg_current(struct pgroup *pg)
  564. {
  565. assert(pg != NULL);
  566. if ((pg->flags & PGLOST) || pg->index >= pg->count)
  567. return (NULL);
  568. switch (pg->entries[pg->index]->type) {
  569. case PEITEM:
  570. return (&pg->entries[pg->index]->u.e);
  571. case PEGRP:
  572. return (pg_current(&pg->entries[pg->index]->u.g));
  573. }
  574. abort();
  575. }
  576. struct pgroup *
  577. pg_parent(struct pgroup *pg, struct pitem *e)
  578. {
  579. struct pgroup *r;
  580. size_t i;
  581. assert(pg != NULL && e != NULL);
  582. for (i = 0; i < pg->count; i++)
  583. switch (pg->entries[i]->type) {
  584. case PEITEM:
  585. if (&pg->entries[i]->u.e == e)
  586. return (pg);
  587. break;
  588. case PEGRP:
  589. if ((r = pg_parent(&pg->entries[i]->u.g, e))
  590. != NULL)
  591. return (r);
  592. break;
  593. default:
  594. abort();
  595. }
  596. return (NULL);
  597. }
  598. void
  599. pg_reset(struct pgroup *pg)
  600. {
  601. size_t i;
  602. assert(pg != NULL);
  603. if (pg->count == 0)
  604. return;
  605. for (i = 0; i < pg->count; i++)
  606. if (pg->entries[i]->type == PEGRP)
  607. pg_reset(&pg->entries[i]->u.g);
  608. pg->index = 0;
  609. switch (pg->type) {
  610. case PGNORM:
  611. break;
  612. case PGSHUF:
  613. memshuffle(pg->entries, pg->count,
  614. sizeof(pg->entries[0]));
  615. break;
  616. case PGRAND:
  617. break;
  618. default:
  619. abort();
  620. }
  621. pg->flags |= PGLOST;
  622. }
  623. struct pitem *
  624. pg_search(struct pgroup *pg, void *cmp, int type, int loop)
  625. {
  626. struct pitem *r = NULL;
  627. struct pitem *e;
  628. size_t i;
  629. size_t n;
  630. assert(pg != NULL && cmp != NULL);
  631. switch (pg->type) {
  632. case PGNORM:
  633. /* FALLTHROUGH */
  634. case PGSHUF:
  635. for (i = pg->index; i < pg->count; i++)
  636. switch (pg->entries[i]->type) {
  637. case PEITEM:
  638. if (i == pg->index)
  639. break;
  640. if (plcmp_call(cmp,
  641. pg->entries[i]->u.e.path, type)
  642. == 0)
  643. return (&pg->entries[i]->u.e);
  644. break;
  645. case PEGRP:
  646. if ((r = pg_search(&pg->entries[i]->u.g,
  647. cmp, type, loop)) != NULL)
  648. return (r);
  649. break;
  650. default:
  651. abort();
  652. }
  653. if (!loop)
  654. break;
  655. if (pg->type == PGSHUF)
  656. goto rand;
  657. for (i = 0; i < pg->index; i++)
  658. switch (pg->entries[i]->type) {
  659. case PEITEM:
  660. if (plcmp_call(cmp,
  661. pg->entries[i]->u.e.path, type)
  662. == 0)
  663. return (&pg->entries[i]->u.e);
  664. break;
  665. case PEGRP:
  666. if ((r = pg_search(&pg->entries[i]->u.g,
  667. cmp, type, loop)) != NULL)
  668. return (r);
  669. break;
  670. default:
  671. abort();
  672. }
  673. break;
  674. case PGRAND:
  675. rand:
  676. for (i = 0, n = 1; i < pg->count; i++) {
  677. e = NULL;
  678. switch (pg->entries[i]->type) {
  679. case PEITEM:
  680. if (plcmp_call(cmp,
  681. pg->entries[i]->u.e.path, type)
  682. == 0)
  683. e = &pg->entries[i]->u.e;
  684. break;
  685. case PEGRP:
  686. e = pg_search(&pg->entries[i]->u.g, cmp,
  687. type, loop);
  688. break;
  689. default:
  690. abort();
  691. }
  692. if (e != NULL && (n == 1 ||
  693. arc4random_uniform(n) == 0)) {
  694. r = e;
  695. n++;
  696. }
  697. }
  698. break;
  699. default:
  700. abort();
  701. }
  702. return (r);
  703. }
  704. int
  705. pg_goto(struct pgroup *pg, struct pitem *e)
  706. {
  707. assert(pg != NULL && e != NULL);
  708. if (pg->type == PGRAND)
  709. pg->index = 0;
  710. for (; pg->index < pg->count; pg->index++)
  711. switch (pg->entries[pg->index]->type) {
  712. case PEITEM:
  713. if (&pg->entries[pg->index]->u.e == e)
  714. return (0);
  715. break;
  716. case PEGRP:
  717. if (pg_goto(&pg->entries[pg->index]->u.g, e)
  718. == 0)
  719. return (0);
  720. break;
  721. default:
  722. abort();
  723. }
  724. return (-1);
  725. }
  726. void
  727. hl_init(struct hlist *hl, size_t size)
  728. {
  729. assert(hl != NULL);
  730. assert(SIZE_MAX / size >= sizeof(hl->entries[0]));
  731. if (size > 0) {
  732. if ((hl->entries =
  733. malloc(size * sizeof(hl->entries[0]))) == NULL)
  734. err(EX_OSERR, "hl_init");
  735. } else
  736. hl->entries = NULL;
  737. hl->size = size;
  738. hl->begin = 0;
  739. hl->end = 0;
  740. hl->index = 0;
  741. hl->lost = 0;
  742. }
  743. void
  744. hl_fini(struct hlist *hl)
  745. {
  746. assert(hl != NULL);
  747. while (hl_remove(hl, hl->entries[hl->begin]) == 0)
  748. /* do nothing */;
  749. if (hl->entries != NULL) {
  750. free(hl->entries);
  751. hl->entries = NULL;
  752. }
  753. hl->size = 0;
  754. hl->begin = 0;
  755. hl->end = 0;
  756. hl->index = 0;
  757. hl->lost = 0;
  758. }
  759. void
  760. hl_append(struct hlist *hl, struct pitem *e)
  761. {
  762. assert(hl != NULL);
  763. if (hl->size == 0)
  764. return;
  765. assert(hl->index != hl->begin ||
  766. (hl->end + 1) % hl->size != hl->begin);
  767. hl->entries[hl->end] = e;
  768. if (hl->index == hl->end)
  769. hl->index = (hl->index + 1) % hl->size;
  770. hl->end = (hl->end + 1) % hl->size;
  771. if (hl->end == hl->begin)
  772. hl->begin = (hl->begin + 1) % hl->size;
  773. }
  774. int
  775. hl_remove(struct hlist *hl, struct pitem *e)
  776. {
  777. size_t i;
  778. size_t j;
  779. assert(hl != NULL);
  780. for (i = hl->begin, j = hl->begin; i != hl->end;
  781. i = (i + 1) % hl->size)
  782. if (hl->entries[i] == e) {
  783. if (i == hl->index)
  784. hl->lost = 1;
  785. if (i + (i < hl->begin ? hl->size : 0) <
  786. hl->index + (hl->index < hl->begin ?
  787. hl->size : 0) || hl->index == hl->end)
  788. hl->index = (hl->index + hl->size - 1) %
  789. hl->size;
  790. } else {
  791. hl->entries[j] = hl->entries[i];
  792. j = (j + 1) % hl->size;
  793. }
  794. hl->end = j;
  795. if (hl->index + (hl->index < hl->begin ? hl->size : 0) >
  796. hl->end + (hl->end < hl->begin ? hl->size : 0))
  797. hl->index = hl->end;
  798. return (i != j ? 0 : -1);
  799. }
  800. void
  801. hl_rem(struct hlist *hl, void *cmp, int type)
  802. {
  803. size_t i;
  804. assert(hl != NULL && cmp != NULL);
  805. for (i = hl->begin; i != hl->end; i = (i + 1) % hl->size)
  806. if (plcmp_call(cmp, hl->entries[i]->path, type) == 0) {
  807. (void)hl_remove(hl, hl->entries[i]);
  808. i = (i + hl->size - 1) % hl->size;
  809. }
  810. }
  811. struct pitem *
  812. hl_current(struct hlist *hl)
  813. {
  814. assert(hl != NULL);
  815. if (hl->lost || hl->index == hl->end)
  816. return (NULL);
  817. return (hl->entries[hl->index]);
  818. }
  819. struct pitem *
  820. hl_next(struct hlist *hl)
  821. {
  822. assert(hl != NULL);
  823. if (hl->index == hl->end)
  824. goto ret;
  825. if (!hl->lost)
  826. hl->index = (hl->index + 1) % hl->size;
  827. ret:
  828. hl->lost = 0;
  829. return (hl->index != hl->end ? hl->entries[hl->index] : NULL);
  830. }
  831. struct pitem *
  832. hl_prev(struct hlist *hl)
  833. {
  834. assert(hl != NULL);
  835. hl->lost = 0;
  836. if (hl->index == hl->begin)
  837. return (NULL);
  838. hl->index = (hl->index + hl->size - 1) % hl->size;
  839. return (hl->entries[hl->index]);
  840. }
  841. struct pitem *
  842. hl_search(struct hlist *hl, void *cmp, int type)
  843. {
  844. size_t i;
  845. assert(hl != NULL && cmp != NULL);
  846. for (i = hl->index; i != hl->end; i = (i + 1) % hl->size)
  847. if (plcmp_call(cmp, hl->entries[i]->path, type) == 0)
  848. return (hl->entries[i]);
  849. return (NULL);
  850. }
  851. int
  852. hl_goto(struct hlist *hl, struct pitem *e)
  853. {
  854. for (; hl->index != hl->end;
  855. hl->index = (hl->index + 1) % hl->size)
  856. if (hl->entries[hl->index] == e)
  857. return (0);
  858. return (-1);
  859. }
  860. int
  861. pl_gtype(int flags)
  862. {
  863. switch (flags & PLGTYPE) {
  864. case PLGNORM:
  865. return (PGNORM);
  866. case PLGSHUF:
  867. return (PGSHUF);
  868. case PLGRAND:
  869. return (PGRAND);
  870. }
  871. abort();
  872. }
  873. int
  874. pl_stype(int flags)
  875. {
  876. switch (flags & PLSTYPE) {
  877. case PLSAUTO:
  878. return (PLCMPGLOB);
  879. case PLSCMP:
  880. return (PLCMPNORM);
  881. case PLSGLOB:
  882. return (PLCMPGLOB);
  883. case PLSBRE:
  884. return (PLCMPBRE);
  885. case PLSERE:
  886. return (PLCMPERE);
  887. }
  888. abort();
  889. }
  890. int
  891. de_nodot(const struct dirent *e)
  892. {
  893. assert(e != NULL);
  894. return (strcmp(e->d_name, ".") != 0 &&
  895. strcmp(e->d_name, "..") != 0);
  896. }