core-attr.c

   1 /*
   2  * Copyright Neil Brown ©2015 <neil@brown.name>
   3  * May be distributed under terms of GPLv2 - see file:COPYING
   4  *
   5  * Attributes.
   6  *
   7  * Attributes are attached to text in buffers and to marks and probably
   8  * other things.
   9  * They are simply name=value pairs, stored as strings though direct
  10  * conversion to numbers and Bools is provided.
  11  * Values must be "small".  The name and value together must be less than
  12  * 512 bytes, and there is probably some padding in there.  If you get
  13  * even close to this limit you are doing something wrong.
  14  * Larger strings need to be stored elsewhere with some sort of indirect.
  15  * (Hmmm.. this excludes file names - is that a good idea?)
  16  *
  17  * Attributes are stored in a list sorted by attribute name.  Strings
  18  * of digits in the name sort like the number they represent, so "6hello"
  19  * comes before "10world".  When such a number compares against a single
  20  * non-digit character the char comes first.
  21  *
  22  * Attributes for text are stored in one list for a section of text.
  23  * Each attribute is prefixed by the offset where the attribute applies.
  24  *
  25  * The offsets are really byte offsets - the text is utf-8.
  26  *
  27  * When attributes are stored on non-text objects they don't have
  28  * a number prefix.
  29  *
  30  */
  31
  32 #include <stdlib.h>
  33 #include <malloc.h>
  34 #include <string.h>
  35 #include <ctype.h>
  36 #include "core.h"
  37
  38 struct attrset {
  39         unsigned short  size, /* space allocated */
  40                         len;  /* space used */
  41         struct attrset *next;
  42         char            attrs[0];
  43 };
  44
  45 #if defined(TEST_ATTR_ADD_DEL)
  46 #define MAX_ATTR_SIZE (64 - sizeof(struct attrset))
  47 #else
  48 #define MAX_ATTR_SIZE (512 - sizeof(struct attrset))
  49 #endif
  50
  51 static struct attrset *newattr(struct attrset *old, int size)
  52 {
  53         struct attrset *set = realloc(old, sizeof(struct attrset) + size);
  54         set->size = size;
  55         if (old == NULL) {
  56                 set->len = 0;
  57                 set->next = NULL;
  58         }
  59         return set;
  60 }
  61
  62 /* attr_cmp just deals with bytes and ASCII digits, so it is
  63  * not aware for wchars
  64  */
  65 static int getcmptok(char **ap)
  66 {
  67         char *a = *ap;
  68         char c = *a++;
  69         int i;
  70         if (!isdigit(c)) {
  71                 *ap = a;
  72                 return c;
  73         }
  74         i = c - '0';
  75         while (isdigit(*a)) {
  76                 c = *a++;
  77                 i = i*10 + (c - '0');
  78         }
  79         *ap = a;
  80         return i+256;
  81 }
  82
  83 /* Compare 'a' and 'b' treating strings of digits as numbers.
  84  * If bnum >= 0, it is used as a leading number on 'b'.
  85  */
  86 static int attr_cmp(char *a, char *b, int bnum)
  87 {
  88         while (*a && *b) {
  89                 int ai, bi;
  90                 ai = getcmptok(&a);
  91                 if (bnum >= 0) {
  92                         bi = bnum + 256;
  93                         bnum = -1;
  94                         if (*a == ' ')
  95                                 a++;
  96                 } else
  97                         bi = getcmptok(&b);
  98                 if (ai < bi)
  99                         return -1;
 100                 if (ai > bi)
 101                         return 1;
 102         }
 103         if (*a)
 104                 return 1;
 105         if (*b)
 106                 return -1;
 107         return 0;
 108 }
 109
 110 #ifdef TEST_ATTR_CMP
 111 #include <stdlib.h>
 112 #include <stdio.h>
 113 struct {char *a, *b; int result;} test[] = {
 114         { "hello", "there", -1},
 115         { "6hello", "10world", -1},
 116         { "0005six", "5six", 0},
 117         { "ab56", "abc", 1},
 118 };
 119 int main(int argc, char *argv[])
 120 {
 121         int i;
 122         int rv = 0;
 123         for (i = 0; i < sizeof(test)/sizeof(test[0]); i++) {
 124                 if (attr_cmp(test[i].a, test[i].b, -1) == test[i].result)
 125                         printf("%s <-> %s = %d OK\n",
 126                                test[i].a, test[i].b, test[i].result);
 127                 else {
 128                         printf("%s <-> %s = %d, not %d\n",
 129                                test[i].a, test[i].b, attr_cmp(test[i].a,
 130                                                               test[i].b, -1),
 131                                test[i].result);
 132                         rv = 1;
 133                 }
 134         }
 135         exit(rv);
 136 }
 137
 138 #endif
 139
 140 static int __attr_find(struct attrset ***setpp, char *key, int *offsetp, int keynum)
 141 {
 142         struct attrset **setp = *setpp;
 143         struct attrset *set = *setp;
 144         int i;
 145
 146         if (!set)
 147                 return -1;
 148         *offsetp = 0;
 149         while (set->next &&
 150                attr_cmp(set->next->attrs, key, keynum) <= 0) {
 151                 setp = &set->next;
 152                 set = *setp;
 153         }
 154         *setpp = setp;
 155
 156         for (i = 0; i < set->len; ) {
 157                 int cmp = attr_cmp(set->attrs + i, key, keynum);
 158                 if (cmp >= 0) {
 159                         *offsetp = i;
 160                         *setpp = setp;
 161                         return cmp;
 162                 }
 163                 i += strlen(set->attrs + i) + 1;
 164                 i += strlen(set->attrs + i) + 1;
 165         }
 166         *offsetp = i;
 167         return 1;
 168 }
 169
 170 int attr_del(struct attrset **setp, char *key)
 171 {
 172         int offset = 0;
 173         int cmp;
 174         int len;
 175         struct attrset *set;
 176
 177         cmp = __attr_find(&setp, key, &offset, -1);
 178
 179         if (cmp)
 180                 /* Not found */
 181                 return 0;
 182         set = *setp;
 183         len = strlen(set->attrs + offset) + 1;
 184         len += strlen(set->attrs + offset + len) + 1;
 185         memmove(set->attrs + offset,
 186                 set->attrs + offset + len,
 187                 set->len - (offset + len));
 188         set->len -= len;
 189         if (set->len == 0) {
 190                 *setp = set->next;
 191                 free(set);
 192         }
 193         return 1;
 194 }
 195
 196 char *attr_get_str(struct attrset *set, char *key, int keynum)
 197 {
 198         struct attrset **setp = &set;
 199         int offset = 0;
 200         int cmp = __attr_find(&setp, key, &offset, keynum);
 201
 202         if (cmp != 0)
 203                 return NULL;
 204         set = *setp;
 205         offset += strlen(set->attrs + offset) + 1;
 206         return set->attrs + offset;
 207 }
 208
 209 char *attr_find(struct attrset *set, char *key)
 210 {
 211         return attr_get_str(set, key, -1);
 212 }
 213
 214 int attr_set_str_key(struct attrset **setp, char *key, char *val, int keynum)
 215 {
 216         int offset = 0;
 217         int cmp;
 218         struct attrset *set;
 219         unsigned int len;
 220         char nkey[22];
 221         int nkeylen = 0;
 222
 223         cmp = __attr_find(&setp, key, &offset, keynum);
 224
 225         if (cmp == 0) {
 226                 /* Remove old value */
 227                 set = *setp;
 228                 len = strlen(set->attrs + offset) + 1;
 229                 len += strlen(set->attrs + offset + len) + 1;
 230                 memmove(set->attrs + offset,
 231                         set->attrs + offset + len,
 232                         set->len - (offset + len));
 233                 set->len -= len;
 234         }
 235         if (!val)
 236                 return cmp;
 237         set = *setp;
 238         if (keynum >= 0) {
 239                 snprintf(nkey, sizeof(nkey), "%d ", keynum);
 240                 nkeylen = strlen(nkey);
 241         }
 242         len = nkeylen + strlen(key) + 1 + strlen(val) + 1;
 243         if (set == NULL || set->len + len > set->size) {
 244                 /* Need to re-alloc or alloc new */
 245                 if (!set) {
 246                         set = newattr(NULL, len);
 247                         *setp = set;
 248                 } else if (set->len + len <= MAX_ATTR_SIZE) {
 249                         /* Just make this block bigger */
 250                         set = newattr(set, set->len + len);
 251                         *setp = set;
 252                 } else if (offset + len <= MAX_ATTR_SIZE) {
 253                         /* split following entries in separate block */
 254                         struct attrset *new = newattr(NULL, set->len - offset);
 255
 256                         new->next = set->next;
 257                         set->next = new;
 258                         new->len = set->len - offset;
 259                         set->len = offset;
 260                         memcpy(new->attrs, set->attrs + offset,
 261                                new->len);
 262                 } else {
 263                         /* Split follow in entries and store new entry there */
 264                         struct attrset *new = newattr(NULL, set->len - offset + len);
 265
 266                         new->next = set->next;
 267                         set->next = new;
 268                         new->len = set->len - offset;
 269                         set->len = offset;
 270                         memcpy(new->attrs, set->attrs + offset,
 271                                new->len);
 272                         set = new;
 273                         offset = 0;
 274                 }
 275         }
 276         memmove(set->attrs + offset + len, set->attrs + offset, set->len - offset);
 277         strncpy(set->attrs + offset, nkey, nkeylen);
 278         strcpy(set->attrs + offset + nkeylen, key);
 279         strcpy(set->attrs + offset + nkeylen + strlen(key) + 1, val);
 280         set->len += len;
 281         return cmp;
 282 }
 283
 284 int attr_set_str(struct attrset **setp, char *key, char *val)
 285 {
 286         return attr_set_str_key(setp, key, val, -1);
 287 }
 288
 289 #if defined(TEST_ATTR_ADD_DEL) || defined(TEST_ATTR_TRIM)
 290 void attr_dump(struct attrset *set)
 291 {
 292         printf("DUMP ATTRS:\n");
 293         while (set) {
 294                 int i;
 295                 printf(" %d of %d:\n", set->len, set->size);
 296                 for (i = 0; i < set->len; ) {
 297                         printf("  %3d: \"%s\"", i, set->attrs + i);
 298                         i += strlen(set->attrs+i) + 1;
 299                         printf(" -> \"%s\"\n", set->attrs + i);
 300                         i += strlen(set->attrs+i) + 1;
 301                 }
 302                 set = set->next;
 303         }
 304         printf("END DUMP\n");
 305 }
 306 #endif
 307
 308 #ifdef TEST_ATTR_ADD_DEL
 309 enum act { Add, Remove, Find };
 310 struct action {
 311         enum act act;
 312         char *key;
 313         char *val;
 314 } actions[] = {
 315         { Add, "Hello", "world"},
 316         { Add, "05 Foo", "Bar" },
 317         { Add, "1 Bold", "off" },
 318         { Add, "9 Underline", "on" },
 319         { Remove, "Hello", NULL },
 320         { Find, "5 Foo", "Bar" },
 321         { Add, "20 Thing", "Stuff" },
 322         { Add, "01 Bold", "on" },
 323         { Add, "1 StrikeThrough", "no" },
 324         { Add, "2 StrikeThrough", "no" },
 325         { Find, "1 StrikeThrough", "no" },
 326         { Find, "5 Foo", "Bar" },
 327         { Add, "1 Nextthing", "nonono" },
 328 };
 329
 330 int main(int argc, char *argv[])
 331 {
 332         int i;
 333         int rv = 0;
 334         struct attrset *set = NULL;
 335         for (i = 0; i < sizeof(actions)/sizeof(actions[0]); i++) {
 336                 struct action *a = &actions[i];
 337                 char *v;
 338                 switch(a->act) {
 339                 case Add:
 340                         attr_set_str(&set, a->key, a->val); continue;
 341                 case Remove:
 342                         if (attr_del(&set, a->key) == 0) {
 343                                 printf("Action %d: Remove %s: failed\n",
 344                                        i, a->key);
 345                                 rv = 1;
 346                                 break;
 347                         }
 348                         continue;
 349                 case Find:
 350                         v = attr_find(set, a->key);
 351                         if (!v || strcmp(v, a->val) != 0) {
 352                                 printf("Action %d: Find %s: Found %s\n",
 353                                        i, a->key, v);
 354                                 rv = 1;
 355                                 break;
 356                         }
 357                         continue;
 358                 }
 359                 break;
 360         }
 361         attr_dump(set);
 362         exit(rv);
 363 }
 364 #endif
 365
 366 /* Have versions that take and return numbers, '-1' for 'not found' */
 367 int attr_find_int(struct attrset *set, char *key)
 368 {
 369         char *val = attr_find(set, key);
 370         unsigned long rv;
 371         char *end;
 372
 373         if (!val)
 374                 return -1;
 375         rv = strtoul(val, &end, 10);
 376         if (end == val || *end)
 377                 return -1;
 378         return rv;
 379 }
 380
 381 int attr_set_int(struct attrset **setp, char *key, int val)
 382 {
 383         char sval[22];
 384
 385         sprintf(sval, "%d", val);
 386         return attr_set_str(setp, key, sval);
 387 }
 388
 389 #ifdef TEST_ATTR_INT
 390 int main(int argc, char *argv[])
 391 {
 392         struct attrset *set = NULL;
 393
 394         attr_set_int(&set, "One", 1);
 395         attr_set_int(&set, "Twelve", 12);
 396         attr_set_int(&set, "Four", 4);
 397         if (attr_find_int(set, "One") +
 398             attr_find_int(set, "Twelve") +
 399             attr_find_int(set, "Four")
 400             != 17) {
 401                 printf("Didn't find One, Twelve, Four\n");
 402                 exit(2);
 403         }
 404         if (attr_find_int(set, "Three") != -1) {
 405                 printf("Surprisingly found Three\n");
 406                 exit(2);
 407         }
 408         exit(0);
 409 }
 410 #endif
 411
 412 void attr_free(struct attrset **setp)
 413 {
 414         struct attrset *set = *setp;
 415         *setp = NULL;
 416         while (set) {
 417                 struct attrset *next = set->next;
 418                 free(set);
 419                 set = next;
 420         }
 421 }
 422
 423 /*
 424  * When attributes are attached to a section of text,
 425  * we might want to split the text and so split the attributes.
 426  * So:
 427  * 1- 'trim' all attributes beyond a given key
 428  * 2- copy attributes, subtracting some number from the offset.
 429  *     At offset '0', an empty value deletes the key.
 430  */
 431
 432 void attr_trim(struct attrset **setp, int nkey)
 433 {
 434         char key[22];
 435         int offset;
 436         struct attrset *set;
 437
 438         sprintf(key, "%d", nkey);
 439         __attr_find(&setp, key, &offset, 0);
 440         set = *setp;
 441         if (!set)
 442                 return;
 443         set->len = offset;
 444         if (offset)
 445                 setp = &set->next;
 446         attr_free(setp);
 447 }
 448
 449 struct attrset *attr_copy_tail(struct attrset *set, int nkey)
 450 {
 451         struct attrset *newset = NULL;
 452
 453         for (; set ; set = set->next) {
 454                 int i;
 455                 for (i = 0; i < set->len; ) {
 456                         char *k, *v;
 457                         int n;
 458                         k = set->attrs + i;
 459                         i += strlen(k) + 1;
 460                         v = set->attrs + i;
 461                         i += strlen(v) + 1;
 462                         n = atoi(k);
 463
 464                         if (n <= nkey && *v == '\0')
 465                                 v = NULL;
 466                         attr_set_str_key(&newset, k, v, nkey);
 467                 }
 468         }
 469
 470         return newset;
 471 }
 472
 473 /* Collect the attributes in effect at a given pos and return
 474  * a new set with the new alternate numeric prefix, or nothing if '-1'
 475  */
 476 struct attrset *attr_collect(struct attrset *set, unsigned int pos,
 477                              int prefix)
 478 {
 479         struct attrset *newset = NULL;
 480         char kbuf[512];
 481
 482         for (; set ; set = set->next) {
 483                 int i;
 484                 for (i = 0; i < set->len; ) {
 485                         char *k, *v, *e;
 486                         unsigned long n;
 487                         k = set->attrs + i;
 488                         i += strlen(k) + 1;
 489                         v = set->attrs + i;
 490                         i += strlen(v) + 1;
 491                         n = strtoul(k, &e, 10);
 492
 493                         if (n > pos)
 494                                 goto done;
 495                         while (*e == ' ')
 496                                 e++;
 497                         if (prefix >= 0) {
 498                                 snprintf(kbuf, 512, "%d %s", prefix, e);
 499                                 e = kbuf;
 500                         }
 501                         if (*v == '\0')
 502                                 v = NULL;
 503                         attr_set_str(&newset, e, v);
 504                 }
 505         }
 506 done:
 507         return newset;
 508 }
 509
 510 #ifdef TEST_ATTR_TRIM
 511
 512 char *keys[] = {
 513         "1 Bold", "2 Bold", "5 Bold", "10 Bold",
 514         "0 Colour", "3 Colour", "08 Colour", "12 Colour",
 515         "2 Invis", "4 Invis", "6 Invis", "9 Invis",
 516 };
 517
 518 int main(int argc, char *argv[])
 519 {
 520         int i;
 521         struct attrset *set = NULL;
 522         struct attrset *newset, *new2;
 523
 524         for (i = 0; i < sizeof(keys)/sizeof(keys[0]); i++)
 525                 attr_set_str(&set, keys[i], keys[i], -1);
 526
 527         newset = attr_copy_tail(set, 5);
 528         attr_trim(&set, 5);
 529         new2 = attr_collect(newset, 9, 4);
 530         attr_dump(set);
 531         attr_dump(newset);
 532         attr_dump(new2);
 533         exit(0);
 534 }
 535 #endif
 536
 537 /*
 538 Iterator for set.
 539 */